#!/usr/bin/python3
# -*- coding: utf-8 -*-

def bubbleSort(arr):
    n = len(arr)

    # 遍历所有数组元素
    for i in range(n):

        # Last i elements are already in place
        for j in range(0, n-i-1):

            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# arr[] --> 排序数组
# low  --> 起始索引
# high  --> 结束索引

# 快速排序函数
def quickSort(arr, start = 0, end = None):
    if end is None:
        end = len(arr) - 1
    if end <= start:
        return(arr)
    i,j = start,end
    ref = arr[start]
    while j > i:
        if arr[j] >= ref:
            j = j - 1
        else:
            arr[i],arr[j],arr[i+1] = arr[j],arr[i+1],arr[i]
            i = i + 1
    quickSort(arr,start = start,end = i - 1)
    quickSort(arr,start = i + 1,end = end)
    return(arr)


def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    # 创建临时数组
    L = [0] * (n1)
    R = [0] * (n2)

    # 拷贝数据到临时数组 arrays L[] 和 R[]
    for i in range(0, n1):
        L[i] = arr[l + i]

    for j in range(0, n2):
        R[j] = arr[m + 1 + j]

    # 归并临时数组到 arr[l..r]
    i = 0     # 初始化第一个子数组的索引
    j = 0     # 初始化第二个子数组的索引
    k = l     # 初始归并子数组的索引

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # 拷贝 L[] 的保留元素
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # 拷贝 R[] 的保留元素
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1


def mergeSort(arr, l, r):
    if l < r:

        m = int((l+(r-1))/2)

        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)

def choiceSort(arr, n):
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        # print("每走一遍")
        # print(arr)

def shellSort(arr, n):
    gap = int(n / 2)
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = int(gap / 2)

def countSort(strarr):
    output = [0 for i in range(256)]
    count = [0 for i in range(256)]
    ans = ["" for _ in strarr]
    for i in strarr:
        count[ord(i)] += 1
    for i in range(256):
        count[i] += count[i - 1]
    for i in range(len(strarr)):
        output[count[ord(strarr[i])] - 1] = strarr[i]
        count[ord(strarr[i])] -= 1
    for i in range(len(strarr)):
        ans[i] = output[i]
    return ans

arr = [64, 34, 25, 12, 22, 11, 90]
print("给定数字数组")
print(arr)
# strarr = "awewfbawefwhqwuhwhueufih"
# print("给定字符数组")
# print(strarr)
n = len(arr)

# bubbleSort(arr)
# print ("冒泡排序后的数字数组:")
# print (arr)

quickSort(arr)
print ("快速排序后的数字数组:")
print (arr)

# mergeSort(arr, 0, n-1)
# print("归并排序后的数字数组")
# print(arr)

# choiceSort(arr, n)
# print("选择排序后的数字数组")
# print(arr)

# shellSort(arr, n)
# print("希尔排序")
# print(arr)

# ans = countSort(strarr)
# print("计数排序后的字符数组")
# print(ans)